package main

import (
	"fmt"
	"math/rand"
	"time"
)

// 22.约瑟夫环问题：编号为 1-N 的 N 个士兵围坐在一起形成一个圆圈，
//	从编号为 1 的士兵开始依次报数（1，2，3…这样依次报），
//	数到 k 的 士兵会被杀掉出列，之后的士兵再从 1 开始报数。
//	直到最后剩下一士兵，求这个士兵的编号。

// 胜利者士兵
func jose(n, k int) int {
	//一个人一个人的数，即为步长为1约瑟夫环的问题
	//递归分析，每一圈n都会递减1的情况
	//所以应分析出P(n,k)与P(n-1,k)的关系
	//归纳f(n,3)：
	//当n=1时，序列为1的特殊情况直接为，即f(1,3)=1。
	//当n=2时，序列为1,2，则胜利者编号为2；f(2,3)=2=(1+3-1)%2+1=[f(1,3)+3-1]%2+1
	//当n=3时，序列为1,2,3,则胜利者编号为2，f(3,3)=2=(2+3-1)%3+1=[f(2,3)+3-1]%3+1
	//当n=4时，序列为1,2,3,4,则胜利者编号为1，f(4,3)=1=(2+2)%4+1=[f(3,3)+3-1]%4+1
	//当n=5时，序列为1,2,3,4,5，则胜利者编号为4，f(5,3)=4=(1+2)%5+1=[f(4,3)+3-1]%5+1，结论成立。
	//归约出胜利者的递推公式：f(n,m)=[f(n-1,m)+m]%n
	if n == 1 {
		return n
	}
	return (jose(n-1, k)+k-1)%n + 1
}

func main() {
	rand.Seed(time.Now().UnixNano()) //按时间初始化随机数种子

	n := rand.Intn(200) + 100 //随机生成100~200个士兵
	k := rand.Intn(100)       //随机选择一个100以内的杀人序号
	fmt.Println(n, "个士兵，每数到", k, "就被杀,经过多轮后剩一个士兵的编号为", jose(n, k))
}
